/*
题目：二叉搜索树的后序遍历序列
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
https://leetcode.cn/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/
 */
public class Offer33 {
    public boolean verifyPostorder(int[] postorder) {
        //单调栈
        Stack<Integer> stack = new Stack<> ();
        int upper = Integer.MAX_VALUE;
        for (int i = postorder.length - 1; i >= 0; i--) {
            if (postorder[i] >= upper) {
                return false;
            }
            while (!stack.isEmpty() && stack.peek() > postorder[i]) {
                upper = stack.pop();//弹出
            }
            stack.push(postorder[i]);
        }

        return true;
    }
}
